第2回講義へようこそ。このコースの全体的な目標を確認した後、アルゴリズム設計の基本となるデータ構造である「配列」と「リンクリスト」について学びます。データ構造が、アルゴリズム設計の基盤となるものです：配列とリンクリスト。
配列とリンクリストは、メモリ上でのデータの整理方法として最も基本的かつ重要な手段であり、連続と分散のストレージ管理における根本的な対立関係を象徴しています。
定義：データ構造とは、効率的なアクセスと変更を可能にするために、データを特定の形式で整理・保存する仕組みのことです。
- 配列は要素を連続連続したメモリ領域に格納し、要素のアドレスを直接計算できるようにします。
- リンクリストは要素を分散分散したメモリ領域に格納し、明示的なポインタのみで接続されています。
- 配列のアクセスは直接インデックス参照（$O(1)$）ですが、リンクリストのアクセスには走査（トラバーサル）（$O(n)$）が必要です。
- 配列での挿入・削除には要素のシフトが必要となり、結果として$O(n)$の計算量になります。
- リンクリストでの挿入・削除は、ポインタの再リンクだけで済み、位置 $i$ がわかっている場合、$O(1)$ の時間で実行可能です。
- リンクリストは、各ノードにデータに加えてメモリオーバーヘッド`next` ポインタを保持しなければならないため、より高いメモリオーバーヘッドが発生します。
計算量の比較
| 特徴 | 配列 | 単方向リンクリスト |
|---|---|---|
| メモリ割り当て | 連続（固定ブロックサイズ $n$） | 分散（動的ポインタ） |
| アクセス時間 | $O(1)$ | $O(n)$ |
| 挿入・削除 | $O(n)$ | $O(1)$（位置 $i$ が既知の場合） |
| メモリオーバーヘッド | 最小限（データのみ） | 高め（データ + nextポインタ） |